package monotonicQueue;

import java.util.Deque;
import java.util.LinkedList;

public class Main {
	public static void main(String[] args) {
		//目标数组
		int[] nums = {1,3,-1,-3,5,3,6,7};
		//区间长度k
		int k=3;
		int[] ans = maxSlidingWindow(nums,3);
		
		for(int i=0;i<ans.length;i++) {
			System.out.printf("%d,", ans[i]);
		}
		System.out.println();
		
		ans = minSlidingWindow(nums,3);
		for(int i=0;i<ans.length;i++) {
			System.out.printf("%d,", ans[i]);
		}
		System.out.println();
		
	}
	
	//k长度滑动窗口最大值
	public static int[] maxSlidingWindow(int[] nums, int k) {
		//实例化双向队列
        Deque<Integer> queue = new LinkedList<>();
        //存放区间最值，数组长度为：目标数组长度减区间长度加一
        int[] ans = new int[nums.length-k+1];
        //遍历原始数组
        for(int i = 0; i < nums.length; i++){
        	//单调队列入队操作第一步：删除队尾小于等于待入队数值的项，注意队列保存的是下标不是具体元素
            while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){
                queue.removeLast();
            }
            //单调队列入队操作第一步：放入队尾，注意队列保存的是下标不是具体元素
            queue.add(i);
            //如果队头的下标在区间范围外了，移除队头元素
            if(queue.peekFirst() <= i - k){
                queue.removeFirst();
            }
            
            //此时[i-k,i]区间内的最大值就是队列头的值，
            //注意获取值后不要出队列
            if(i >= k-1){
                ans[i-k+1] = nums[queue.peekFirst()];
            }
        }
        return ans;
    }
	
	//k长度滑动窗口最小值
	public static int[] minSlidingWindow(int[] nums, int k) {
		//实例化双向队列
        Deque<Integer> queue = new LinkedList<>();
        //存放区间最值，数组长度为：目标数组长度减区间长度加一
        int[] ans = new int[nums.length-k+1];
        //遍历原始数组
        for(int i = 0; i < nums.length; i++){
        	//单调队列入队操作第一步：删除队尾大于等于待入队数值的项，注意队列保存的是下标不是具体元素
            while(!queue.isEmpty() && nums[queue.peekLast()] >= nums[i]){
                queue.removeLast();
            }
            //单调队列入队操作第一步：放入队尾，注意队列保存的是下标不是具体元素
            queue.add(i);
            //如果队头的下标在区间范围外了，移除队头元素
            if(queue.peekFirst() <= i - k){
                queue.removeFirst();
            }
            
            //此时[i-k,i]区间内的最大值就是队列头的值，
            //注意获取值后不要出队列
            if(i >= k-1){
                ans[i-k+1] = nums[queue.peekFirst()];
            }
        }
        return ans;
    }
}

